import java.util.Arrays;

public class P11_13 {

    //数学法
    public int missingNumber3(int[] nums) {
        int sum = 0;
        for(int i = 1 ;i <= nums.length; i++){
            sum+=i;
        }
        int rel = 0;
        for(int i = 0;i<nums.length;i++){
            rel+=nums[i];
        }
        return sum-rel;
    }

    //排序法
    public int missingNumber2(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0 ; i < nums.length ; i++ ){
            if(nums[i]!=i){
                return i;
            }
        }
        return nums.length;
    }

    //映射法1
    public int missingNumber1(int[] nums) {
        int[] arr = new int[nums.length+1];
        for(int i = 0; i<nums.length;i++){
            int tmp = nums[i];
            arr[tmp]++;
        }
        for(int i = 0 ;i<arr.length;i++){
            if(arr[i]==0){
                return i;

            }
        }
        return -1;
    }

    //映射法2,相同长度下布尔数组所占空间比整型数组小
    public int missingNumber(int[] nums) {
        boolean[] b = new boolean[nums.length+1];
        for(int i = 0; i<nums.length;i++){
            b[nums[i]] = true;
        }
        for(int i = 0;i<b.length;i++){
            if(b[i]==false) return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] a = {1};
        rotate(a,3);
        for (int i:a) {
            System.out.print(a[i]+" ");
        }
        Arrays.sort(a);
    }

    //反转数组法
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        revers(nums,0,n-1);//把后面的数组搬到前面去
        revers(nums,0,k%n-1);//把走到前面的数组顺序调正
        revers(nums,k%n,n-1);//把后面的数组调正

    }
    public static void revers(int[] arr,int left,int right){

        while (left<right){
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }

    //通过测试用例;循环数组取余法
    public static void rotate2(int[] nums, int k) {
        int[] arr = new int[nums.length];
        for(int i = 0;i<nums.length;i++){
            arr[(i+k)%nums.length]=nums[i];
        }
        for(int i = 0; i<nums.length ;i++){
            nums[i] = arr[i];
        }
    }

    //(自己做的)可以但超时
    public static void rotate1(int[] nums, int k) {
        int[] arr = new int[nums.length];
        while(k>0) {
            for (int i = 1; i < nums.length; i++) {
                if (i == 1) {
                    int tmp = nums.length - 1;
                    arr[0] = nums[tmp];
                }
                arr[i] = nums[i - 1];

            }
            for (int i = 0; i < nums.length; i++) {
                nums[i] = arr[i];
            }
            k--;
        }
    }
}
